/*
 * @lc app=leetcode.cn id=1220 lang=cpp
 *
 * [1220] 统计元音字母序列的数目
 */
#include "include.h"
// @lc code=start
using LL = long long;
using Mat = vector<vector<LL>>;

class Solution {
public:     
    Mat multiply(const Mat & matrixA, const Mat & matrixB, LL mod) {
        int m = matrixA.size();
        int n = matrixB[0].size();
        Mat res(m, vector<LL>(n, 0));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < matrixA[i].size(); ++k) {
                    res[i][j] = (res[i][j] + matrixA[i][k] * matrixB[k][j]) % mod;
                }
            }
        }
        return res;
    }
     
    Mat fastPow(const Mat & matrix, LL n, LL mod) {
        int m = matrix.size();
        Mat res(m, vector<LL>(m, 0));
        Mat curr = matrix;

        for (int i = 0; i < m; ++i) {
            res[i][i] = 1;
        }
        for (int i = n; i != 0; i >>= 1) {
            if (i & 1) {
                res = multiply(curr, res, mod);
            }
            curr = multiply(curr, curr, mod);
        }
        return res;
    }

    int countVowelPermutation(int n) {
        LL mod = 1e9 + 7;
        Mat factor =
        {
            {0, 1, 0, 0, 0}, 
            {1, 0, 1, 0, 0}, 
            {1, 1, 0, 1, 1}, 
            {0, 0, 1, 0, 1}, 
            {1, 0, 0, 0, 0}
        };
        Mat res = fastPow(factor, n - 1, mod);
        long long ans = 0;
        for (int i = 0; i < 5; ++i) {
            ans = (ans + accumulate(res[i].begin(), res[i].end(), 0LL)) % mod;
        }
        return  ans;
    }
};

class SolutionIdiot {
public:
    int countVowelPermutation(int n) {
        n_ = n;

        // DP_[length-1][charactor_index]
        DP_.resize(n_, std::vector<long long>(5, 0));

        // length = 1
        for (auto& num : DP_[0]) {
            num = 1;
        }

        // resize()修改vector大小和新增元素，不影响已有元素
        // DP_[0].resize(5, 1);

        for (int i=1;i<n_;++i) {
            for (int j=0;j<5;++j) {
                int candidateCount = regularTable_[j][0];
                // sum
                for (int k=0;k<candidateCount;++k) {
                    int temp = regularTable_[j][k+1];
                    DP_[i][j] += DP_[i-1][temp];
                }

                // mod before final sum, during each step
                DP_[i][j] %= 1000000007;
            }
        }

        for (int i=0;i<5;++i) {
            result_ += DP_[n_-1][i];
        }

        return result_ % 1000000007;
    }
private:
    std::vector<std::vector<long long>> DP_;

    int n_;
    long long result_ = 0;

    int regularTable_[5][6] = {
        {1, 1, 0, 0, 0, 0}, // a 0
        {2, 0, 2, 0, 0, 0}, // e 1
        {4, 0, 1, 3, 4, 0}, // i 2
        {2, 2, 4, 0, 0, 0}, // o 3
        {1, 0, 0, 0, 0, 0}, // u 4
        // {5, 0, 1, 2, 3, 4}, // ~ 5
    };
};
// @lc code=end

int main() {
    Solution test;
    test.countVowelPermutation(1);
}